package com.xiyou.week03.chart;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 684. 冗余连接
 * <p>
 * 树可以看成是一个连通且 无环 的 无向 图。
 * <p>
 * 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
 * <p>
 * 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
 *
 * @ClassName：FindRedundantConnection
 * @Author：西柚
 * @Date：2022/1/16 11:25 下午
 * @Versiion：1.0
 */
public class FindRedundantConnection {

    private static List<List<Integer>> to;
    private static boolean[] visited;
    private static boolean hasCycle;

    /**
     * 输入: edges = [[1,2], [1,3], [2,3]]
     * 输出: [2,3]
     *
     * @param edges
     * @return
     */
    public static int[] findRedundantConnection(int[][] edges) {
        int n = 0;
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            n = Math.max(n, Math.max(x, y));
        }
        to = new ArrayList<>();
        visited = new boolean[n + 1];
        for (int i = 0; i < n + 1; i++) {
            visited[i] = false;
            to.add(new ArrayList<>());
        }

        List<Integer> list;
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            // 出边数组加边方法
            to.get(x).add(y);
            to.get(y).add(x);
            hasCycle = false;

            dfs(x, 0);
            if (hasCycle) {
                return edge;
            }
        }
        return new int[]{};
    }


    /**
     * 图的深度优先遍历判断环的模板
     *
     * @param x
     * @param fa
     */
    private static void dfs(int x, int fa) {
        if (to.get(x) == null) {
            return;
        }
        visited[x] = true;
        // 出边数组访问X能到的周围点的方法
        for (int y : to.get(x)) {
            if (y == fa) {
                continue;
            }
            if (!visited[y]) {
                dfs(y, x);
            } else {
                hasCycle = true;
            }
        }
        visited[x] = false;
    }

    public static void main(String[] args) {
//        int[][] edges = new int[][]{{1, 2}, {1, 3}, {2, 3}};
        int[][] edges = new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
        System.out.println(Arrays.toString(findRedundantConnection(edges)));
    }

}
